class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):
    def sortLinkedList(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        pre_mut_neg = ListNode(0)
        pre_mut_pos = ListNode(0)
        pre_pos = pre_mut_pos
        node = head
        while node:
            if node.val >= 0:
                pre_pos.next = node
                pre_pos = node
                node = node.next
            else:
                next_node = pre_mut_neg.next
                pre_mut_neg.next = node
                new_node = node.next
                node.next = next_node
                node = new_node
        pre_pos.next = None
        prev = pre_mut_neg
        node = pre_mut_neg.next
        if pre_mut_pos.next:
            while node:
                prev = node
                node = node.next
            prev.next = pre_mut_pos.next
            return pre_mut_neg.next
        else:
            return pre_mut_neg.next


